package leetcode.code;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.HelpDebug;

public class Solution386 {

	public List<Integer> lexicalOrder(int n) {
		List<Integer> ans = new ArrayList<>();
		this.f(0, 1, n, ans);
		return ans;
	}

	/**
	 * 以base为基数, 从start开始添加到个位数, <=n的结果添加到ans中
	 *
	 * @param base
	 * @param start
	 * @param n
	 * @param ans
	 */
	private void f(int base, int start, int n, List<Integer> ans) {
		if (base > n)
			return;
		for (int i = start; i < 10; i++) {
			int num = i + base;
			if (num <= n) {
				ans.add(num);
				this.f(num * 10, 0, n, ans);
			}
		}
	}

	public static void main(String[] args) {
		Solution386 so = new Solution386();
		List<Integer> ans = so.lexicalOrder(13);
		HelpDebug.print(ans);
	}

}
